'''
https://leetcode.cn/problems/implement-trie-prefix-tree/?envType=study-plan-v2&envId=top-interview-150
'''

MAXN = 150001
tree = [[0 for _ in range(26)] for _ in range(MAXN)]
passed = [0 for _ in range(MAXN)]
ended = [0 for _ in range(MAXN)]
cnt = 1

class Trie:
    def __init__(self):
        global cnt, tree, passed, ended
        for i in range(1, cnt + 1):
            tree[i] = [0 for _ in range(26)]
        passed[1:cnt+1] = [0] * cnt
        ended[1:cnt+1] = [0] * cnt
        cnt = 1
        # self.tree = [[0 for _ in range(26)] for _ in range(MAXN)]
        # self.passed = [0 for _ in range(MAXN)]
        # self. ended = [0 for _ in range(MAXN)]
        # self.cnt = 1

    def insert(self, word: str) -> None:
        global cnt, tree, passed, ended
        # cnt, tree, passed, ended = self.cnt, self.tree, self.passed, self.ended
        cur = 1
        passed[cur] += 1
        for c in word:
            path = ord(c) - ord('a')
            if not tree[cur][path]:
                # self.cnt += 1
                # tree[cur][path] = self.cnt
                cnt += 1
                tree[cur][path] = cnt
            cur = tree[cur][path]
            passed[cur] += 1
        ended[cur] += 1

    def search(self, word: str) -> bool:
        global tree, ended
        # cnt, tree, passed, ended = self.cnt, self.tree, self.passed, self.ended
        cur = 1
        for c in word:
            path = ord(c) - ord('a')
            if not tree[cur][path]:
                return False
            cur = tree[cur][path]
        return ended[cur] > 0

    def startsWith(self, prefix: str) -> bool:
        global tree, passed
        # cnt, tree, passed, ended = self.cnt, self.tree, self.passed, self.ended
        cur = 1
        for c in prefix:
            path = ord(c) - ord('a')
            if not tree[cur][path]:
                return False
            cur = tree[cur][path]
        return passed[cur] > 0

class Node:
    def __init__(self):
        self.passed = 0
        self.ended = 0
        self.next = {}

class Trie2:
    def __init__(self):
        self.root = Node()

    def insert(self, word: str) -> None:
        cur = self.root
        cur.passed += 1
        for c in word:
            if c not in cur.next:
                cur.next[c] = Node()
            cur = cur.next[c]
            cur.passed += 1
        cur.ended += 1

    def search(self, word: str) -> bool:
        cur = self.root
        for c in word:
            if c not in cur.next:
                return False
            cur = cur.next[c]
        return cur.ended > 0

    def startsWith(self, prefix: str) -> bool:
        cur = self.root
        for c in prefix:
            if c not in cur.next:
                return False
            cur = cur.next[c]
        return cur.passed > 0

obj = Trie2()
obj.insert('apple')
print(obj.search('apple'))
print(obj.search('app'))
print(obj.startsWith('app'))
obj.insert('app')
print(obj.search('app'))

obj = Trie2()
obj.insert('ab')
print(obj.search('a'))
print(obj.startsWith('a'))
print(obj.search('ab'))